home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / circuits / irsim-ca.2 / irsim-ca / irsim-cap-9.2 / src / irsim / sstep.c < prev    next >
C/C++ Source or Header  |  1993-01-15  |  8KB  |  252 lines
  1. /* 
  2.  *     ********************************************************************* 
  3.  *     * Copyright (C) 1988, 1990 Stanford University.                     * 
  4.  *     * Permission to use, copy, modify, and distribute this              * 
  5.  *     * software and its documentation for any purpose and without        * 
  6.  *     * fee is hereby granted, provided that the above copyright          * 
  7.  *     * notice appear in all copies.  Stanford University                 * 
  8.  *     * makes no representations about the suitability of this            * 
  9.  *     * software for any purpose.  It is provided "as is" without         * 
  10.  *     * express or implied warranty.  Export of this software outside     * 
  11.  *     * of the United States of America may require an export license.    * 
  12.  *     ********************************************************************* 
  13.  */
  14.  
  15. #include <stdio.h>
  16. #include "net.h"
  17. #include "defs.h"
  18. #include "globals.h"
  19.  
  20. /* event-driven switch-level simulation step Chris Terman 7/84 */
  21.  
  22. /* the following file contains most of the declarations, conversion
  23.  * tables, etc, that depend on the particular representation chosen
  24.  * for node values.  This info is automatically created for interval
  25.  * value sets (see Chapter 5 of my thesis) by gentbl.c.  Except
  26.  * for the charged_state and thev_value arrays and their associated
  27.  * code, the rest of the code is independent of the value set details...
  28.  */
  29. #include "stables.c"
  30.  
  31.  
  32. private    int    sc_thev();
  33.  
  34.  
  35. /* tables for converting node value to corresponding charged state */
  36. private    char    charged_state[4] = 
  37.   {
  38.     CL, CHCL, CHCL, CH
  39.   };
  40.  
  41. private    char    xcharged_state[4] = 
  42.   {
  43.     cL, cHcL, cHcL, cH
  44.   };
  45.  
  46. /* table for converting node value to corresponding value state */
  47. private    char    thev_value[4] = 
  48.   {
  49.     DL, DHDL, DHDL, DH
  50.   };
  51.  
  52.  
  53.  
  54. /* calculate new value for node and its electrical neighbors */
  55. public void switch_model( n )
  56.   nptr    n;
  57.   {
  58.     register nptr  this, next;
  59.  
  60.     nevals++;
  61.  
  62.     if( n->nflags & VISITED )
  63.     BuildConnList( n );
  64.  
  65.     /* for each node on list we just built, recompute its value using a
  66.      * recursive tree walk.  If logic state of new value differs from
  67.      * logic state of current value, node is added to the event list (or
  68.      * if it's already there, just the eval field is updated).  If logic
  69.      * states do not differ, node's value is updated on the spot and any
  70.      * pending events removed.
  71.      */
  72.     for( this = n; this != NULL; this = this->nlink )
  73.       {
  74.     register int    newval, queued;
  75.     register evptr  e;
  76.     register long   delta;
  77.     long            tau;
  78.  
  79.     if( this->nflags & INPUT )
  80.         newval = this->npot;
  81.     else
  82.       {
  83.         newval = logic_state[sc_thev( this, this->nflags & WATCHED ? 1 : 0 )];
  84.         switch( newval )
  85.           {
  86.         case LOW :
  87.             delta = this->tphl;
  88.             break;
  89.         case X :
  90.             delta = 0;
  91.             break;
  92.         case HIGH :
  93.             delta = this->tplh;
  94.             break;
  95.           }
  96.         tau = delta;
  97.         if( delta == 0 )    /* no zero-delay events */
  98.         delta = 1;
  99.       }
  100.  
  101.     if( not (this->nflags & INPUT) )
  102.       {
  103.         /* 
  104.          * Check to see if this new value invalidates other events. 
  105.          * Since this event has newer info about the state of the network,
  106.          * delete transitions scheduled to come after it.
  107.          */
  108.         while( (e = this->events) != NULL and e->ntime >= cur_delta + delta )
  109.           {
  110.         /* 
  111.          * Do not try to kick the event scheduled at cur_delta if
  112.          * newval is equal to this->npot because that event sets
  113.          * this->npot, but its consequences has not been handled yet.
  114.          * Besides, this event will not be queued. 
  115.          *
  116.          * However, if there is event scheduled now but driving to a 
  117.          * different value, then kick it becuase we will enqueue this 
  118.          * one, and source/drain of transistors controlled by this
  119.          * node will be re-evaluated. At worst, some extra computation
  120.          * will be carried out due to VISITED flags set previously.
  121.          */
  122. /*        if( e->ntime == cur_delta and newval == this->npot ) */
  123.         if( e->ntime == (cur_delta + delta) and e->eval == newval )
  124.             break;
  125.         PuntEvent( this, e );
  126.           }
  127.         /*
  128.          * Now see if the new value is different from the last value
  129.          * scheduled for the node. If there are no pending events then
  130.          * just use the current value.
  131.          */
  132.  
  133.         if( newval != ((e == NULL) ? this->npot : e->eval) )
  134.           {
  135.         queued = 1;
  136.         enqueue_event( this, newval, delta, tau );
  137.           }
  138.         else
  139.         queued = 0;
  140.  
  141.         if( (this->nflags & WATCHED) and (debug & (DEBUG_DC | DEBUG_EV)) )
  142.           {
  143.         lprintf( stdout, " [event %s->%c @ %.1f] ", pnode( cur_node ),
  144.           vchars[ cur_node->npot ], d2ns( cur_delta ) );
  145.  
  146.         lprintf( stdout, queued ? "causes transition for" : "sets" );
  147.         lprintf( stdout, " %s: %c -> %c (delay = %2.1fns)\n",
  148.           pnode( this ), vchars[ this->npot ], vchars[ newval ],
  149.           d2ns( delta ) );
  150.           }
  151.       }
  152.       }
  153.     /* undo connection list */
  154.     for( this = n; this != NULL; this = next )
  155.       {
  156.     next = this->nlink;
  157.     this->nlink = NULL;
  158.       }
  159.   }
  160.  
  161.  
  162. /* compute new value for a node using recursive tree walk.  We start off by
  163.  * assuming that node is charged to whatever logic state it had last.  The
  164.  * contribution of each path leading away from the node is computed
  165.  * recursively and merged with accumulated result.  After all paths have been
  166.  * examined, return the answer!
  167.  *
  168.  * Notes: The node-visited flag is set during the computation of a node's
  169.  *      value. This keeps the tree walk exanding outward; loops are avoided.
  170.  *      Since the flag is cleared at the end of the computation, all paths
  171.  *      through the network will eventually be explored.  (If it had been
  172.  *      left set, only a single path through a particular cycle would be
  173.  *      explored).
  174.  *
  175.  *        In order to speed up the computation, the result of each recursive
  176.  *      call is cached.  There are 2 caches associated with each transistor:
  177.  *      the source cache remembers the value of the subnetwork that includes
  178.  *      the transistor and everything attached to its drain. The drain cache
  179.  *      is symmetrical.  Use of these caches reduces the complexity of the
  180.  *      new-value computation from O(n**2) to O(n) where n is the number of
  181.  *      nodes in the connection list built in the new_value routine.
  182.  */
  183. private int sc_thev( n, level )
  184.   register nptr  n;
  185.   int            level;
  186.   {
  187.     register tptr  t;
  188.     register lptr  l;
  189.     register int   result;
  190.  
  191.     if( n->nflags & INPUT )
  192.       {
  193.     result = thev_value[n->npot];
  194.     goto done;
  195.       }
  196.  
  197.     /* initial values and stuff... */
  198.     n->nflags |= VISITED;
  199.     result = (n->ngate == NULL) ? xcharged_state[n->npot] :
  200.                   charged_state[n->npot];
  201.  
  202.     for( l = n->nterm; l != NULL; l = l->next )
  203.       {
  204.     t = l->xtor;
  205.  
  206.       /* don't bother with off transistors */
  207.     if( t->state == OFF )
  208.         continue;
  209.  
  210.     /* for each non-off transistor, do nothing if node on other side has
  211.      * its visited flag set (this is how cycles are detected).  Otherwise
  212.      * check cache and use value found there, if any.  As a last resort,
  213.      * actually compute value for network on other side of transistor,
  214.      * transmit the value through the transistor, and save that result
  215.      * for later use.
  216.      */
  217.     if( n == t->source )
  218.       {
  219.         if( not (t->drain->nflags & VISITED) )
  220.           {
  221.         if( t->dcache.i == EMPTY )
  222.             t->dcache.i = transmit[sc_thev( t->drain, level ? level + 1 : 0 )][t->state];
  223.         result = smerge[result][t->dcache.i];
  224.           }
  225.       }
  226.     else
  227.       {
  228.         if( not (t->source->nflags & VISITED) )
  229.           {
  230.         if( t->scache.i == EMPTY )
  231.             t->scache.i = transmit[sc_thev( t->source, level ? level + 1 : 0 )][t->state];
  232.         result = smerge[result][t->scache.i];
  233.           }
  234.       }
  235.       }
  236.  
  237.     n->nflags &= ~VISITED;
  238.  
  239.   done :
  240.     if( (debug & (DEBUG_DC | DEBUG_TW)) and level > 0 )
  241.       {
  242.     register int  i;
  243.  
  244.     lprintf( stdout, "  " );
  245.     for( i = level; --i > 0;  )
  246.         lprintf( stdout, " " );
  247.     lprintf( stdout, "sc_thev(%s) = %s\n", pnode(n), node_values[result]);
  248.       }
  249.  
  250.     return( result );
  251.   }
  252.